package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.Node;

/**
 * 检查平衡树
 *
 * @author Mr_wenpan@163.com 2021/12/22 11:52
 */
public class CheckBalancedBinaryTree {

    public static void main(String[] args) {

    }

    public static boolean checkBbt(Node head) {
        if (head == null) {
            return true;
        }
        BbtResult res = isBbt(head);
        return res.isBbt;
    }

    public static BbtResult isBbt(Node head) {
        if (head == null) {
            return new BbtResult(true, 0);
        }
        // 向左右孩子要结果
        BbtResult leftRes = isBbt(head.left);
        BbtResult rightRes = isBbt(head.right);
        // 整合左右孩子的结果
        boolean isBbt = leftRes.isBbt && rightRes.isBbt && (Math.abs(leftRes.high - rightRes.high) < 2);
        int high = Math.max(leftRes.high, rightRes.high) + 1;
        return new BbtResult(isBbt, high);
    }

    static class BbtResult {
        boolean isBbt;
        int high;

        public BbtResult(boolean isBbt, int high) {
            this.isBbt = isBbt;
            this.high = high;
        }
    }

}
